package com.leetcode.LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC15_2 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> arrayLists = new ArrayList<>();
        Arrays.sort(nums);

        int start = 0, end = 0;

        for (int i = 0; i < nums.length - 2; i++) {
            if(i==0||nums[i]!=nums[i-1]) {
                start = i + 1;
                end = nums.length - 1;
                while (start < end) {
                    if (start < end && nums[i] + nums[start] + nums[end] == 0) {
                        arrayLists.add(Arrays.asList(nums[i], nums[start], nums[end]));
                        start++;
                        end--;
                        while (start < end && nums[start] == nums[start - 1]) {
                            start++;
                        }
                        while (start < end && nums[end] == nums[end + 1]) {
                            end--;
                        }
                    } else if (start < end && nums[i] + nums[start] + nums[end] < 0) {
                        start++;
                    } else {
                        end--;
                    }
                }
            }
        }
        return arrayLists;
    }

    public static void main(String[] args) {
        LC15_2 lc15_2 = new LC15_2();
        List<List<Integer>> lists = lc15_2.threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        System.out.println(lists);
    }
}
